# 二叉树的堂兄弟节点

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(4)
a.left = b
a.right = c
b.left = d


class Solution:
    def isCousins(self, root, x, y):
        # x 的信息
        x_parent, x_depth, x_found = None, None, False
        # y 的信息
        y_parent, y_depth, y_found = None, None, False
        
        def dfs(node, depth, parent):
            if not node:
                return
            
            nonlocal x_parent, y_parent, x_depth, y_depth, x_found, y_found
            
            # 根
            if node.val == x:
                x_parent, x_depth, x_found = parent, depth, True
            elif node.val == y:
                y_parent, y_depth, y_found = parent, depth, True

            # 如果两个节点都找到了，就可以提前退出遍历
            # 即使不提前退出，对最坏情况下的时间复杂度也不会有影响
            if x_found and y_found:
                return
            
            # 左
            dfs(node.left, depth + 1, node)

            if x_found and y_found:
                return

            # 右
            dfs(node.right, depth + 1, node)

        dfs(root, 0, None)
        return x_depth == y_depth and x_parent != y_parent

s = Solution()
boolean = s.isCousins(a, 4, 3)
print(boolean)
